With the explosive growth of the Internet, the table scale required for routers and switches in a network has been rapidly increasing, and the speed-up of table search has been demanded. As means for solving this problem from the aspect of hardware, a ternary content addressable memory (TCAM) attracts a lot of attention.
For example, Japanese Patent Application Laid-Open Publication No. 2003-272386 (Patent Document 1) discloses a structure of the TCAM cell using two dynamic storage cells for storing three values of ‘0’/‘1’/‘X’ (don't care). By this structure, the occupied area of the cell can be reduced and the increase in capacity can be achieved, and at the same time, low power consumption and speed-up of search operation can be achieved.
In addition, for example, “IEEE 2004 Symposium on VLSI Circuits, Digest of Technical Papers” June 2004, pp. 382 to 385 (Non-patent Document 1) discloses an encoding method of entry or search key and a memory array structure to achieve the CAM which can solve the problems of capacity shortage and increase in power consumption in the TCAM. In this technology, an encoding method called one-hot-spot block code is used.
In the TCAM, “entry” is usually used as a term that corresponds to “word” popularly used in a DRAM and a SRAM. Since “entry” is the term which indicates information stored in each “word”, the storage information is called “entry” and comparison information is called “search key” in accordance with customary practice in this specification.